Field of the Disclosure
The present disclosure relates generally to processors and more particularly to vertex coloring at a processor.
Description of the Related Art
Vertex coloring, also known as graph coloring, is widely used in a variety of applications to efficiently assign processor resources. The resource assignment process begins by forming a graph to represent each of a plurality of processor resources (e.g., hardware resources and software structures at a processor). The graph is composed of a set of vertices and connections between the vertices, where each vertex represents a corresponding processor resource and each connection represents a relationship between processor resources. Vertex coloring is initiated by assigning “colors” to the vertices of the graph based on a set of constraints or rules for resource assignment, where the constraints represent a limitation of the processor resources. For example, in some scenarios each vertex of the graph can represent an execution unit of a processor, wherein the connections between the vertices indicate that the corresponding execution units share a register or other resource that cannot be used simultaneously by two different execution units. The color assigned to each vertex represents a time slot for execution of a specified task. To prevent execution units from using a shared resource simultaneously, the colors assigned to the vertices are constrained so that no two connected vertices share the same color. Vertex coloring can be an efficient way to assign resources for a processor having many resources and many relationships between these resources. However, conventional vertex coloring techniques can take excessively long to complete, limiting processor efficiency.